package com.zwj.interview.排序;

import java.util.Arrays;

/**
 * 归并排序（https://www.cnblogs.com/fivestudy/p/10075421.html）
 */
public class MergeSort {

    public static int[] sort(int[] a,int low,int high){
        int mid=(low+high)/2;
        if(low<high){
            //先进行分开排序，最后进行归并
           sort(a,low,mid);
           sort(a,mid+1,high);
           //左右归并
            merge(a,low,mid,high);
        }
        return a;
    }



    public static void merge(int[] a,int low,int mid,int high){
        //归并排序需要一个辅助数组，这个数组需要和原数组一样大小
        int[] temp=new int[high-low+1];
        int i=low;
        int j=mid+1;
        //新数组的下标
        int k=0;
        //把较小的数先移到新数组中
        while(i<=mid && j<=high){
            if(a[i]<a[j]){
                temp[k++]=a[i++];
            }else{
                temp[k++]=a[j++];
            }
        }
        //把左边剩余的数移入数组
        while(i<=mid){
            temp[k++]=a[i++];
        }
        //把右边边剩余的数移入数组
        while(j<=high){
           temp[k++]=a[j++];
         }
        //把新数组中的数覆盖nums数组
        System.arraycopy(temp,0,a,low,high-low+1);
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(sort(new int[]{4,1,5,6,2,7,8,3},0,7)));
    }

}
